#include <stdio.h>
#include <stdlib.h>

/* https://c.biancheng.net/view/3432.html */

//分别定义平衡因子数
#define LH +1
#define EH 0
#define RH -1
typedef int ElemType;
typedef enum {false, true} bool;
//定义二叉排序树
typedef struct BSTNode
{
    /* data */
    ElemType data;
    //balance flag
    int bf;
    struct BSTNode * lchild, * rchild;
}BSTNode, * BSTree;

//对以 p 为根结点的二叉树做右旋处理，令 p 指针指向新的树根结点
void R_Rotate(BSTree * p) {
    //借助文章中的图 5 所示加以理解，其中结点 A 为 p 指针指向的根结点
    BSTree lc = (*p)->lchild;
    (*p)->lchild = lc->rchild;
    lc->rchild = *p;
    *p = lc;
}

////对以 p 为根结点的二叉树做左旋处理，令 p 指针指向新的树根结点
void L_Rotate(BSTree * p) {
    //借助文章中的图 6 所示加以理解，其中结点 A 为 p 指针指向的根结点
    BSTree rc = (*p)->rchild;
    (*p)->rchild = rc->lchild;
    rc->lchild = *p;
    *p = rc;
}

//对以指针 T 所指向结点为根结点的二叉树作左子树的平衡处理，令指针 T 指向新的根结点
void LeftBalance(BSTree * T) {
    BSTree lc, rd;
    lc = (*T)->lchild;
    /* 查看以 T 的左子树为根结点的子树，失去平衡的原因，如果 bf 值为 1 ，则说明添加在左子树为根结点的左子树中，需要对其进行右旋处理；反之，如果 bf 值为 -1，说明添加在以左子树为根结点的右子树中，需要进行双向先左旋后右旋的处理 */
    switch(lc->bf) {
        case LH:
            (*T)->bf = lc->bf = EH;
            R_Rotate(*T);
            break;
        case RH:
            rd = lc->rchild;
            switch(rd->bf) {
                case LH:
                    /* 根节点平衡因子改为1 */
                    (*T)->bf = RH;
                    /* 左孩子节点平衡因子改为0 */
                    lc->bf = EH;
                    break;
                case EH:
                    (*T)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    lc->bf = LH;
                    break;
            }
            /* 双向先左旋后右旋 */
            rd->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
            break;
        default:
            break;
    }
}

//右子树的平衡处理同左子树的平衡处理完全类似
void RightBalance(BSTree * T) {
    BSTree lc, rd;
    lc = (*T)->rchild;
    switch(lc->bf) {
        /* T右子树为根结点的右子树上插入结点 */
        case RH:
            (*T)->bf = lc->bf = EH;
            L_Rotate(T);
            break;
        /* bf 值为 -1，T右子树为根结点的左子树上插入结点 */
        case LH:
            rd = lc->lchild;
            switch(rd->bf) {
                case LH:
                    (*T)->bf = EH;
                    lc->bf = RH;
                    break;
                case EH:
                    (*T)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    lc->bf = LH;
                    break;
                default:
                    break;
            }
            rd->bf = EH;
            R_Rotate(&(*T)->rchild);
            L_Rotate(T);
            break;
        default:
            break;
    }
}

int InsertAVL(BSTree * T, ElemType e, bool * taller) {
    //如果本身为空树，则直接添加 e 为根结点
    if((*T) == NULL) {
        (*T) = (BSTree)malloc(sizeof(BSTNode));
        (*T)->bf = EH;
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        *taller = true;
    } else if(e == (*T)->data) {
        //如果二叉排序树中已经存在 e ，则不做任何处理
        *taller = false;
        return 0;
    } else if( e < (*T)->data) {
        //如果 e 小于结点 T 的数据域，则插入到 T 的左子树中
        //如果插入过程，不会影响树本身的平衡，则直接结束
        if(!InsertAVL(&(*T)->lchild, e, taller)) {
            return 0;
        }
        //判断插入过程是否会导致整棵树的深度 +1
        if(*taller) {
            //判断根结点 T 的平衡因子是多少，由于是在其左子树添加新结点的过程中导致失去平衡，所以当 T 结点的平衡因子本身为 1 时，需要进行左子树的平衡处理，否则更新树中各结点的平衡因子数
            switch((*T)->bf) {
                case LH:
                    LeftBalance(T);
                    *taller = false;
                    break;
                case EH:
                    (*T)->bf = LH;
                    *taller = true;
                    break;
                case RH:
                    (*T)->bf = EH;
                    *taller = false;
                    break;
            }
        }
    } else if(e > (*T)->data) {
        //同样，当 e>T->data 时，需要插入到以 T 为根结点的树的右子树中，同样需要做和以上同样的操作
        if(!InsertAVL(&(*T)->rchild, e, taller)) {
            return 0;
        }
        if(*taller) {
            switch((*T)->bf) {
                case LH:
                    (*T)->bf = EH;
                    *taller = false;
                    break;
                case EH:
                    (*T)->bf = RH;
                    *taller = true;
                    break;
                case RH:
                    RightBalance(T);
                    *taller = false;
                    break;
            }
        }
    }
    return 1;
}

//判断现有平衡二叉树中是否已经具有数据域为 e 的结点
bool findNode(BSTree root, ElemType e, BSTree * pos) {
    BSTree pt = root;
    (*pos) = NULL;
    while (pt)
    {
        /* code */
        if(pt->data == e) {
            //找到节点，pos指向该节点并返回true
            (*pos) = pt;
            return true;
        } else if(pt->data > e) {
            pt = pt->lchild;
        } else {
            pt = pt->rchild;
        }
    }
    return false;    
}

//中序遍历平衡二叉树
void InorderTra(BSTree root) {
    if(root->lchild) {
        InorderTra(root->lchild);
    }
    printf("%d ",root->data);
    if(root->rchild) {
        InorderTra(root->rchild);
    }
}

int main(int argc, char * argv[]) {
    int i, nArr[] = {1, 23, 45, 34, 98, 9, 4, 35, 23};
    BSTree root = NULL,pos;
    bool taller;
    //用 nArr查找表构建平衡二叉树（不断插入数据的过程）
    for(i = 0; i < 9; i++) {
        InsertAVL(&root, nArr[i], &taller);
    }
    //中序遍历输出
    InorderTra(root);
    //判断平衡二叉树中是否含有数据域为 103 的数据
    if(findNode(root, 103, &pos)) {
        printf("\n%d\n",pos->data);
    } else {
        printf("\nNot find this Node\n");
    }
    return 0;
}